/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class FractionAdditionandSubtraction {
    public String fractionAddition(String expression) {
        List<Character> symbols=new ArrayList<>();
        List<Integer> chids=new ArrayList<>();
        List<Integer> parents=new ArrayList<>();
        int i=0;
        if(Character.isDigit(expression.charAt(0))){
        	symbols.add('+');
        }else {
			symbols.add(expression.charAt(i));
	        i++;
		}
        while (true) {
        	//分子
        	StringBuilder sBuilder=new StringBuilder();
        	char curChar=expression.charAt(i);
        	while (curChar!='/') {
				sBuilder.append(curChar);
        		i++;
        		curChar=expression.charAt(i);
			}
        	chids.add(Integer.parseInt(sBuilder.toString()));

        	//当前为/
        	i++;//下一个数字char
        	curChar=expression.charAt(i);
        	sBuilder=new StringBuilder();
        	while (curChar!='+'&&curChar!='-') {
				sBuilder.append(curChar);
        		i++;
        		if(i==expression.length()){
        			break;
        		}
        		curChar=expression.charAt(i);
			}
        	parents.add(Integer.parseInt(sBuilder.toString()));
        	
        	if(i==expression.length()){
    			break;
    		}
        	//符号
        	symbols.add(curChar);
        	i++;
		}
        
        //计算所有分母的公倍数
        int minB=getBei(parents);
        int sum=0;
        for (int j = 0; j <chids.size(); j++) {
        	if(symbols.get(j)=='+'){
        		sum+=chids.get(j)*(minB/parents.get(j));
        	}else {
        		sum-=chids.get(j)*(minB/parents.get(j));
			}
		}
        if(sum==0){
        	return "0/1";
        }
        
        String reString="";
        if(sum<0){
        	reString+="-";
        	sum=0-sum;
        }
        int yue=yue(sum, minB);
        sum/=yue;
        minB/=yue;
        reString+=sum;
        reString+="/";
        reString+=minB;
        
        return reString;
    }
    
    //x是否有可能超出int
	private int getBei(List<Integer> parents) {
		if(parents.isEmpty())
			return 0;
		
		int x=parents.get(0);
		for (int i = 1; i < parents.size(); i++) {
			int tmp=parents.get(i);
			if(x%tmp==0){
				continue;
			}
			int a=yue(x,tmp);
			x*=tmp/a;
		}
		return x;
	}
	//最大公约数
	private int yue(int x, int tmp) {
		int a=x,b=tmp;
		while (a!=b) {
			if(a>b){
				a-=b;
			}else {
				b-=a;
			}
		}
		return a;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		FractionAdditionandSubtraction fractionAdditionandSubtraction=new FractionAdditionandSubtraction();
		String test="5/3+1/3";
		System.out.println(fractionAdditionandSubtraction.fractionAddition(test));
	}

}
